package a10_动态规划;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a26_单词拆分复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/4/1
 */
public class a26_单词拆分复习2 {
    public static void main(String[] args) {
        a26_单词拆分复习2 test = new a26_单词拆分复习2();
        System.out.println(test.wordBreak("leetcode", Arrays.asList("leet", "code")));
    }
    //dp[i]：长度为i的字符串是否能拆分

    //递推公式：
    //如果dp[j] == true
    //j~i-1出现在wordDict里面
    //那么dp[i]=true

    //初始化：
    //dp[0] = true
    public boolean wordBreak(String s, List<String> wordDict) {
        char[] chars = s.toCharArray();

        boolean[] dp = new boolean[chars.length+1];
        dp[0] = true;

        for (int i = 1; i <= chars.length; i++) {
            for (int j = 0; j < i; j++) {
                if(dp[j] && wordDict.contains(splitArray(chars, j, i - 1))){
                    dp[i] = true;
                }
            }
        }
        return dp[chars.length];
    }

    private String splitArray(char[] chars,int leftIdx,int rightIdx){
        StringBuilder sb = new StringBuilder();
        while (leftIdx <= rightIdx) {
            sb.append(chars[leftIdx]);
            leftIdx++;
        }
        return sb.toString();
    }
}
